package com.practice.recursive;

/**
 * Write a simple regular expression matches: supports regular character, plus
 * ? and * (G)
 */
public class SimpleRE {
	public boolean matches(String pattern, String str) {
		int i = 0;
		while (i < pattern.length() && pattern.charAt(i) != '?'
				&& pattern.charAt(i) != '*')
			i++;

		if (i == pattern.length())
			return pattern.equals(str);

		char c = pattern.charAt(i - 1);
		if (pattern.charAt(i) == '?') {
			return pattern.substring(0, i - 1).equals(str.substring(0, i - 1))
					&& (matches(c + pattern.substring(i + 1), str.substring(i - 1)) 
					|| matches(pattern.substring(i + 1), str.substring(i - 1)));
		}

		// pattern.charAt(i) == '*'
		int j = i - 1;
		while (j < str.length() && str.charAt(j) == c) j++;

		for (int k = j; k >= i - 1; k--) {
			if (matches(pattern.substring(i + 1), str.substring(k)))
				return true;
		}

		return false;
	}
}
